package com.lw.leetcode.binary.a;

import java.util.Arrays;

/**
 * binary
 * LCP 28. 采购方案
 *
 * @Author liw
 * @Date 2021/8/4 21:44
 * @Version 1.0
 */
public class PurchasePlans {

    public static void main(String[] args){
        PurchasePlans test = new PurchasePlans();
        int[] arr = {2,5,3,5};
        int target = 6;
        int i = test.purchasePlans(arr, target);
        System.out.println(i);
    }

    public int purchasePlans(int[] nums, int target) {
        long n = 0;
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            n += (find(nums, target - nums[i] + 1, i - 1));
        }
        return (int) (n % 1000000007);
    }

    private int find (int[] arr, int t, int end) {
        if (arr[0] > t - 1) {
            return 0;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (arr[m] < t) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st + 1;
    }
}
